package com.ww.springboot.boot.algorithm.leetcode2;

import java.util.*;

/**
 * 描述：
 *
 * @author 🧑 ‍wanwei
 * @since 2025-07-02 10:10
 */
public class B2101引爆最多的炸弹 {

    public static void main(String[] args) {
       // int[][] bombs = {{1, 2, 3}, {2, 3, 1}, {3, 4, 2}, {4, 5, 3}, {5, 6, 4}};
        int[][] bombs = {{37207,2653,5261},{40784,59523,20635},{16390,1426,39102},{42236,12,96855},{72839,62027,61667},{60691,58191,48447},{42932,46579,41248},{35868,43119,6870},{41693,98905,17374},{43441,1266,41621}};
        //int[][] bombs = {{1,1,5}, {10,10,5}};
        //int[][] bombs = {{656, 619, 56}, {189, 402, 178}, {513, 373, 276}, {900, 510, 14}, {188, 173, 129}, {512, 178, 251}, {145, 685, 47}, {504, 355, 500}, {554, 131, 214}, {596, 1, 98}, {358, 230, 197}, {88, 758, 155}, {72, 340, 419}, {818, 708, 222}};
        int res = maximumDetonation2(bombs);
        System.out.println(res);
    }

    /**
     * 不仅仅是单线 只要是自己可以引爆的都可以叠加
     * 将所有可引爆的关系全部存储
     * @param bombs
     * @return
     */
    private static int maximumDetonation2(int[][] bombs) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < bombs.length; i++) {
            int[] x = bombs[i];
            for (int j = 0; j < bombs.length; j++) {
                if (j == i) {
                    continue;
                }
                int[] y = bombs[j];
                if (Math.pow(x[0] - y[0], 2) + Math.pow(x[1] - y[1], 2) <= Long.valueOf(x[2]) * Long.valueOf(x[2])) {
                    List<Integer> list = map.get(i);
                    if (list == null) {
                        list = new ArrayList<>();
                    }
                    list.add(j);
                    map.put(i, list);
                }
            }
        }

        if (map.isEmpty()) {
            return 1;
        }
        Map<Integer, Set<Integer>> mapCount = new HashMap<>();
        //遍历map所有key 计算每个key最大引爆数量 并缓存起来 最终筛选出最大的值
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            Integer index = entry.getKey();
            for (Integer r : entry.getValue()) {
                dfs2(index,r,mapCount,map);
            }

        }
        return mapCount.values().stream().map(x -> x.size()).mapToInt(x -> x).max().getAsInt();
    }

    private static void dfs2(Integer index, Integer r, Map<Integer, Set<Integer>> mapCount,Map<Integer, List<Integer>> map) {
        Set<Integer> set = mapCount.get(index);
        if(set == null){
            set = new HashSet<>();
            set.add(index);
            mapCount.put(index, set);
        }
        Set<Integer> set1 = mapCount.get(r);
        if(set1 != null){
            set.addAll(set1);
        }else {
            if(set.add(r)){
                List<Integer> list = map.get(r);
                if(list == null){
                    return;
                }
                for (Integer rr : list) {
                    dfs2(index,rr,mapCount,map);
                }
            }
        }
    }


    /**
     * 不仅仅是单线 只要是自己可以引爆的都可以叠加
     * 将所有可引爆的关系全部存储
     * @param bombs
     * @return
     */
    private static int maximumDetonation(int[][] bombs) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < bombs.length; i++) {
            int[] x = bombs[i];
            for (int j = 0; j < bombs.length; j++) {
                if (j == i) {
                    continue;
                }
                int[] y = bombs[j];
                if (Math.pow(x[0] - y[0], 2) + Math.pow(x[1] - y[1], 2) <= x[2] * x[2]) {
                    List<Integer> list = map.get(i);
                    if (list == null) {
                        list = new ArrayList<>();
                    }
                    list.add(j);
                    map.put(i, list);
                }
            }
        }

        if (map.isEmpty()) {
            return 1;
        }
        Map<Integer, Integer> mapCount = new HashMap<>();
        Map<Integer, String> mapRoute = new HashMap<>();
        //遍历map所有key 计算每个key最大引爆数量 并缓存起来 最终筛选出最大的值
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            Integer index = entry.getKey();
            String route = "->" + index + "->";
            dfs(index, index, route, map, mapCount, mapRoute);
        }

        return mapCount.values().stream().sorted().mapToInt(x -> x).max().getAsInt();
    }

    private static void dfs(int key, int index, String route, Map<Integer, List<Integer>> map, Map<Integer, Integer> mapCount, Map<Integer, String> mapRoute) {
        //System.out.println("key:" + key + " index:" + index + " route:" + route);
        List<Integer> list = map.get(index);
        if (list == null) {
            Integer count = mapCount.getOrDefault(key, 1);
            Integer countNew = route.split("->").length - 1;
            if (countNew > count) {
                mapCount.put(key, countNew);
                mapRoute.put(key, route);
            }
            return;
        }
        for (Integer index1 : list) {
            //重复路径 直接返回
            if (route.contains("->" + index1 + "->")) {
                Integer count = mapCount.getOrDefault(index, 1);
                Integer countNew = route.split("->").length - 1;
                if (countNew > count) {
                    mapCount.put(key, countNew);
                    mapRoute.put(key, route);
                }
                continue;
            }
            //String ss = "key:" + key + " index:" + index1 + " route:" + route;
            dfs(key, index1, route + index1 + "->", map, mapCount, mapRoute);
            //String ss2 = "key:" + key + " index:" + index1 + " route:" + route;
            //System.out.println(ss + " ------ " + ss2);
        }
    }
}
